<!DOCTYPE html>


<html lang="zh-CN">


<head>
  <meta charset="utf-8" />
  <meta name="baidu-site-verification" content="code-kg5UjKJZM2" />
   
  <meta name="keywords" content="活,炼" />
   
  <meta name="description" content="shimmerjordan" />
  
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1" />
  <title>
    蓝桥杯小练 |  丛烨-shimmerjordan
  </title>
  <meta name="generator" content="hexo-theme-ayer">
  
  <link rel="shortcut icon" href="/favicon.ico" />
  
  
<link rel="stylesheet" href="/dist/main.css">

  <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Shen-Yu/cdn/css/remixicon.min.css">
  
<link rel="stylesheet" href="/css/custom.css">

  
  <script src="https://cdn.jsdelivr.net/npm/pace-js@1.0.2/pace.min.js"></script>
  
  

<script type="text/javascript">
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');

ga('create', 'G-Q0DT8B8VJW', 'auto');
ga('send', 'pageview');

</script>



  
<script>
var _hmt = _hmt || [];
(function() {
	var hm = document.createElement("script");
	hm.src = "https://hm.baidu.com/hm.js?6d06f826e125297d4ce0fa7a1449328e";
	var s = document.getElementsByTagName("script")[0]; 
	s.parentNode.insertBefore(hm, s);
})();
</script>


<link rel="alternate" href="/atom.xml" title="丛烨-shimmerjordan" type="application/atom+xml">
</head>

</html>

	<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/font-awesome/css/font-awesome.min.css">
	<script src="https://cdn.jsdelivr.net/gh/stevenjoezhang/live2d-widget@latest/autoload.js"></script>


<body>
  <div id="app">
    
      
    <main class="content on">
      <section class="outer">
  <article
  id="post-蓝桥杯小练"
  class="article article-type-post"
  itemscope
  itemprop="blogPost"
  data-scroll-reveal
>
  <div class="article-inner">
    
    <header class="article-header">
       
<h1 class="article-title sea-center" style="border-left:0" itemprop="name">
  蓝桥杯小练
</h1>
 

    </header>
     
    <div class="article-meta">
      <a href="/2020/01/21/practiceLanqiao/" class="article-date">
  <time datetime="2020-01-21T01:47:23.000Z" itemprop="datePublished">2020-01-21</time>
</a> 
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E8%AF%95%E9%A2%98%E7%BB%83%E4%B9%A0/">试题练习</a>
  </div>
  
<div class="word_count">
    <span class="post-time">
        <span class="post-meta-item-icon">
            <i class="ri-quill-pen-line"></i>
            <span class="post-meta-item-text"> 字数统计:</span>
            <span class="post-count">1.2k</span>
        </span>
    </span>

    <span class="post-time">
        &nbsp; | &nbsp;
        <span class="post-meta-item-icon">
            <i class="ri-book-open-line"></i>
            <span class="post-meta-item-text"> 阅读时长≈</span>
            <span class="post-count">5 分钟</span>
        </span>
    </span>
</div>
 
    </div>
      
    <div class="tocbot"></div>




  
    <div class="article-entry" itemprop="articleBody">
       
  <p>　　记录“蓝桥杯”等赛事的练习，包括真题以及小练等。<br><span id="more"></span></p>
<h1 id="1-计算器模拟"><a href="#1-计算器模拟" class="headerlink" title="1.计算器模拟"></a>1.计算器模拟</h1><h2 id="1-1-问题描述"><a href="#1-1-问题描述" class="headerlink" title="1.1 问题描述"></a>1.1 问题描述</h2><font size=2 face="黑体">

　　模拟程序型计算器，依次输入指令，可能包含的指令有  
　　　1.数字：'NUM X'，X为一个只包含大写字母和数字的字符串，表示一个当前进制的数  
　　　2.运算指令：'ADD','SUB','MUL','DIV','MOD'，分别表示加减乘，除法取商，除法取余  
　　　3.进制转换指令：'CHANGE K'，将当前进制转换为K进制(2≤K≤36)  
　　　4.输出指令：'EQUAL'，以当前进制输出结果  
　　　5.重置指令：'CLEAR'，清除当前数字  

　　指令按照以下规则给出：  
　　　数字，运算指令不会连续给出，进制转换指令，输出指令，重置指令有可能连续给出  
　　　运算指令后出现的第一个数字，表示参与运算的数字。且在该运算指令和该数字中间不会出现运算指令和输出指令  
　　　重置指令后出现的第一个数字，表示基础值。且在重置指令和第一个数字中间不会出现运算指令和输出指令  
　　　进制转换指令可能出现在任何地方  

　　运算过程中中间变量均为非负整数，且小于2^63。  
　　以大写的'A'&#126;'Z'表示10&#126;35  


　　输入格式  
　　　第1行：1个n，表示指令数量  
　　　第2..n+1行：每行给出一条指令。指令序列一定以'CLEAR'作为开始，并且满足指令规则  
　　输出格式  
　　　依次给出每一次'EQUAL'得到的结果  
　　样例输入  
　　　7  
　　　CLEAR  
　　　NUM 1024  
　　　CHANGE 2  
　　　ADD  
　　　NUM 100000  
　　　CHANGE 8  
　　　EQUAL  
　　样例输出  
　　　2040

</font>

<h2 id="1-2-问题分析"><a href="#1-2-问题分析" class="headerlink" title="1.2 问题分析"></a>1.2 问题分析</h2><p>　　由于输入为字符串类型，因此需要将字符串类型的“数字”转化为真实的N进制数方能进行运算。机器将N进制数自动转化为二进制进行运算并得到相应的结果。<br>　　这里我们考虑首先将NUM指令后，也即参与运算的字符数转化为十进制进行运算。在读取到EQUAL指令时再将十进制转化为相应的进制数回显。此外，使用res寄存结果，num变量存储操作数。</p>
<h2 id="1-3-实现代码"><a href="#1-3-实现代码" class="headerlink" title="1.3 实现代码"></a>1.3 实现代码</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;iostream&gt;</span>  </span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;algorithm&gt;</span>  </span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;string&gt;</span>  </span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;cctype&gt;</span>  </span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">long</span> <span class="type">long</span> <span class="title">toNumber</span><span class="params">(string strNum, <span class="type">int</span> radix)</span> </span>&#123;</span><br><span class="line">	<span class="type">long</span> <span class="type">long</span> flagNum = <span class="number">0</span>;</span><br><span class="line">	<span class="type">int</span> len = strNum.<span class="built_in">length</span>();</span><br><span class="line">	<span class="comment">//转换为radix进制数</span></span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; len; i++) &#123;</span><br><span class="line">		<span class="keyword">if</span> (<span class="built_in">isupper</span>(strNum[i]))</span><br><span class="line">			<span class="comment">//当读取到大写字母时</span></span><br><span class="line">			<span class="comment">//注意(strNum - &#x27;A&#x27; + 10)以及(strNum - &#x27;0&#x27;)均可补齐差值部分</span></span><br><span class="line">			flagNum = (strNum[i] - <span class="string">&#x27;A&#x27;</span> + <span class="number">10</span>) + flagNum * radix;</span><br><span class="line">		<span class="keyword">else</span></span><br><span class="line">			flagNum = (strNum[i] - <span class="string">&#x27;0&#x27;</span>) + flagNum * radix;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> flagNum;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function">string <span class="title">toString</span><span class="params">(<span class="type">long</span> <span class="type">long</span> num, <span class="type">int</span> radix)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (num == <span class="number">0</span>)  <span class="keyword">return</span> <span class="string">&quot;0&quot;</span>;</span><br><span class="line">	<span class="type">long</span> <span class="type">long</span> temp;</span><br><span class="line">	string flag;</span><br><span class="line">	<span class="keyword">while</span> (num) &#123;</span><br><span class="line">		temp = num % radix;</span><br><span class="line">		<span class="keyword">if</span> (temp &gt; <span class="number">10</span>)</span><br><span class="line">			<span class="comment">//意味着需要用字母表示对应进制数的数位</span></span><br><span class="line">			flag.<span class="built_in">push_back</span>(temp + <span class="string">&#x27;A&#x27;</span> - <span class="number">10</span>);</span><br><span class="line">		<span class="keyword">else</span></span><br><span class="line">			flag.<span class="built_in">push_back</span>(temp + <span class="string">&#x27;0&#x27;</span>);</span><br><span class="line">		num /= radix;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">reverse</span>(flag.<span class="built_in">begin</span>(), flag.<span class="built_in">end</span>());	<span class="comment">//由于flag.push_back()将字符串倒置放入，这里需要将其倒序</span></span><br><span class="line">	<span class="keyword">return</span> flag;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">(<span class="type">int</span> argc, <span class="type">char</span>* argv[])</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> n;		<span class="comment">//命令行数</span></span><br><span class="line">	<span class="type">int</span> radix = <span class="number">10</span>;	<span class="comment">//默认使用10进制进行中介运算</span></span><br><span class="line">	<span class="type">int</span> p = <span class="number">0</span>;	<span class="comment">//用于操作判断</span></span><br><span class="line">	<span class="type">int</span> clear = <span class="number">1</span>;	<span class="comment">//用于判断CLEAR指令状态</span></span><br><span class="line">	string ord, input_strNum;	<span class="comment">//定义指令以及输入的字符数字</span></span><br><span class="line">	<span class="type">long</span> <span class="type">long</span> res = <span class="number">0</span>, num;</span><br><span class="line">	cin &gt;&gt; n;</span><br><span class="line">	<span class="keyword">while</span> (n--) &#123;</span><br><span class="line">		cin &gt;&gt; ord;</span><br><span class="line">		<span class="keyword">if</span> (!ord.<span class="built_in">compare</span>(<span class="string">&quot;NUM&quot;</span>)) &#123;</span><br><span class="line">			<span class="keyword">if</span> (clear) &#123;</span><br><span class="line">				cin &gt;&gt; input_strNum;</span><br><span class="line">					res = <span class="built_in">toNumber</span>(input_strNum, radix);</span><br><span class="line">					clear = <span class="number">0</span>;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> &#123;</span><br><span class="line">				cin &gt;&gt; input_strNum;</span><br><span class="line">					num = <span class="built_in">toNumber</span>(input_strNum, radix);</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">if</span> (p) &#123;</span><br><span class="line">				<span class="keyword">if</span> (p == <span class="number">1</span>)  res += num;</span><br><span class="line">				<span class="keyword">else</span> <span class="keyword">if</span> (p == <span class="number">2</span>)  res -= num;</span><br><span class="line">				<span class="keyword">else</span> <span class="keyword">if</span> (p == <span class="number">3</span>)  res *= num;</span><br><span class="line">				<span class="keyword">else</span> <span class="keyword">if</span> (p == <span class="number">4</span>)  res /= num;</span><br><span class="line">				<span class="keyword">else</span> <span class="keyword">if</span> (p == <span class="number">5</span>)  res %= num;</span><br><span class="line">				p = <span class="number">0</span>;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span> (!ord.<span class="built_in">compare</span>(<span class="string">&quot;CHANGE&quot;</span>))  cin &gt;&gt; radix;</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span> (!ord.<span class="built_in">compare</span>(<span class="string">&quot;EQUAL&quot;</span>))  cout &lt;&lt; <span class="built_in">toString</span>(res, radix) &lt;&lt; endl;</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span> (!ord.<span class="built_in">compare</span>(<span class="string">&quot;ADD&quot;</span>))  p = <span class="number">1</span>;</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span> (!ord.<span class="built_in">compare</span>(<span class="string">&quot;SUB&quot;</span>))  p = <span class="number">2</span>;</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span> (!ord.<span class="built_in">compare</span>(<span class="string">&quot;MUL&quot;</span>))  p = <span class="number">3</span>;</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span> (!ord.<span class="built_in">compare</span>(<span class="string">&quot;DIV&quot;</span>))  p = <span class="number">4</span>;</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span> (!ord.<span class="built_in">compare</span>(<span class="string">&quot;MOD&quot;</span>))  p = <span class="number">5</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h1 id="2-合根植物"><a href="#2-合根植物" class="headerlink" title="2.合根植物"></a>2.合根植物</h1><h2 id="2-1-问题描述"><a href="#2-1-问题描述" class="headerlink" title="2.1 问题描述"></a>2.1 问题描述</h2><font size=2 face="黑体">
　　w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。  
　　这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。


　　如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？  
输入格式  
　　第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1<m,n<1000）。  
　　接下来一行，一个整数k，表示下面还有k行数据(0<k<100000)  
　　接下来k行，第行两个整数a，b，表示编号为a的小格子和编号为b的小格子合根了。


　　格子的编号一行一行，从上到下，从左到右编号。    
　　比如：5 * 4 的小格子，编号：    
　　　1 2 3 4  
　　　5 6 7 8  
　　　9 10 11 12  
　　　13 14 15 16  
　　　17 18 19 20  
样例输入  
　　　5 4  
　　　16  
　　　2 3  
　　　1 5  
　　　5 9  
　　　4 8  
　　　7 8  
　　　9 10  
　　　10 11  
　　　11 12  
　　　10 14  
　　　12 16  
　　　14 18  
　　　17 18  
　　　15 19  
　　　19 20  
　　　9 13  
　　　13 17  
样例输出  
　　　5    
样例说明  
　　其合根情况参考下图  
　<img src="https://s2.ax1x.com/2020/01/22/1AP9tx.jpg" width="18%" height="20%" />
</font>

<h2 id="2-2-问题分析"><a href="#2-2-问题分析" class="headerlink" title="2.2 问题分析"></a>2.2 问题分析</h2><p>　　这是典型的并查集问题，只需要集合归并后搜索即可。  </p>
<h2 id="2-3-代码实现"><a href="#2-3-代码实现" class="headerlink" title="2.3 代码实现"></a>2.3 代码实现</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> maxn = <span class="number">1e6</span> + <span class="number">10</span>;</span><br><span class="line"><span class="type">int</span> pre[maxn];</span><br><span class="line"></span><br><span class="line"><span class="comment">//初始化Union_Find_set并查集</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">initUFset</span><span class="params">(<span class="type">int</span> n)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; n; i++)  pre[i] = i;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//查找树根</span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">find</span><span class="params">(<span class="type">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">return</span> x == pre[x] ? x : pre[x] = <span class="built_in">find</span>(pre[x]);</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//联合树枝</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">join</span><span class="params">(<span class="type">int</span> x, <span class="type">int</span> y)</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> fx = <span class="built_in">find</span>(x);</span><br><span class="line">	<span class="type">int</span> fy = <span class="built_in">find</span>(y);</span><br><span class="line">	<span class="keyword">if</span> (fx != fy) pre[fy] = fx;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> m, n, k, x, y, total;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d%d%d&quot;</span>, &amp;m, &amp;n, &amp;k);</span><br><span class="line">	total = m * n;</span><br><span class="line">	<span class="built_in">initUFset</span>(total);</span><br><span class="line">	<span class="keyword">while</span> (k--) &#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;x, &amp;y);</span><br><span class="line">		<span class="built_in">join</span>(x, y);</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="type">int</span> ans = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt; total; i++) &#123;</span><br><span class="line">		<span class="keyword">if</span> (<span class="built_in">find</span>(i) == i)  ++ans;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, ans);</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;	</span><br></pre></td></tr></table></figure>
<h2 id="2-4-注释"><a href="#2-4-注释" class="headerlink" title="2.4 注释"></a>2.4 注释</h2><p>　　在Visual Studio 2019中运行代码会出现以下报错：<br>　　<img src="https://s2.ax1x.com/2020/01/22/1AFmfP.jpg" alt="1AFmfP.jpg"><br>　　并非代码bug，这里可考虑尝试以下方法解决编译器报错：<br>　　　方法一：在程序最前面（指在所有#include前的最前）加#define _CRT_SECURE_NO_DEPRECATE；<br>　　　方法二：在程序最前面加#define _CRT_SECURE_NO_WARNINGS；<br>　　　方法三：在程序最前面加#pragma warning(disable:4996)；<br>　　　方法四：把scanf、scanf改为scanf_s、fopen_s，具体方法请百度；<br>　　　方法五：无需在程序最前面加那行代码，只需在新建项目时取消勾选“SDL检查”即可；<br>　　　方法六：若项目已建立好，在项目属性里关闭SDL也行；<br>　　　方法七：在工程项目设置一下就行；将报错那个宏定义放到 项目属性 — C/C++— 预处理器 — 预处理器定义；<br>　　　方法八：在 项目属性 — c/c++ — 命令行 添加：/D _CRT_SECURE_NO_WARNINGS 就行了。  </p>
<h1 id="3-分考场"><a href="#3-分考场" class="headerlink" title="3.分考场"></a>3.分考场</h1><h2 id="3-1-问题描述"><a href="#3-1-问题描述" class="headerlink" title="3.1 问题描述"></a>3.1 问题描述</h2><p><font size=2 face="黑体"><br>　　n个人参加某项特殊考试。<br>　　为了公平，要求任何两个认识的人不能分在同一个考场。<br>　　求是少需要分几个考场才能满足条件。  </p>
<p>输入格式<br>　　第一行，一个整数n(1<n<100)，表示参加考试的人数。  
　　第二行，一个整数m，表示接下来有m行数据  
　　以下m行每行的格式为：两个整数a，b，用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。  
输出格式  
　　一行一个整数，表示最少分几个考场。  
样例输入  
　　5  
　　8  
　　1 2  
　　1 3  
　　1 4  
　　2 3  
　　2 4  
　　2 5  
　　3 4   
　　4 5   
样例输出  
　　5  
</font></p>
<h2 id="3-2-问题分析"><a href="#3-2-问题分析" class="headerlink" title="3.2 问题分析"></a>3.2 问题分析</h2><p>　　采用回溯算法，每次有两种抉择，新建房间和放置入之前的某个房间（需要判断）</p>
<h2 id="3-3-代码实现"><a href="#3-3-代码实现" class="headerlink" title="3.3 代码实现"></a>3.3 代码实现</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">define</span> _CRT_SECURE_NO_WARNINGS</span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> min(a, b) a &gt; b ? b : a  </span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">100</span> + <span class="number">5</span>;</span><br><span class="line"><span class="type">int</span> cnt[N];				<span class="comment">//cnt[i]表示第i个room内人数</span></span><br><span class="line"><span class="type">int</span> relation[N][N];		<span class="comment">//relation[i][j]表示i考生与j考生之间的关系</span></span><br><span class="line"><span class="type">int</span> room[N][N];			<span class="comment">//room[i][j]表示第i个考场内第j个考生</span></span><br><span class="line"><span class="type">int</span> ans = <span class="number">0x3f3f3f3f</span>;	<span class="comment">//最好情况的房间数</span></span><br><span class="line"><span class="type">int</span> n;					<span class="comment">//参加考试的人数</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">solve</span><span class="params">(<span class="type">int</span> curStu, <span class="type">int</span> roomNum)</span> </span>&#123;	<span class="comment">//curStu表示当前学生，roomNum表示当前考场编号</span></span><br><span class="line">	<span class="keyword">if</span> (roomNum &gt; ans)  <span class="keyword">return</span>;	<span class="comment">//已经大于最好情况的ans个房间，剪枝</span></span><br><span class="line">	<span class="keyword">if</span> (curStu &gt; n) &#123;</span><br><span class="line">		ans = <span class="built_in">min</span>(ans, roomNum);</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= roomNum; i++) &#123;	<span class="comment">//判断是否可以放入以前的考场</span></span><br><span class="line">		<span class="type">bool</span> legal = <span class="literal">true</span>;</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">1</span>, len = cnt[i]; j &lt; len; j++) &#123;	<span class="comment">//判断是否和考场内的人相识</span></span><br><span class="line">			<span class="keyword">if</span> (relation[room[i][j]][curStu] == <span class="number">1</span>) &#123;</span><br><span class="line">				legal = <span class="literal">false</span>;				<span class="comment">//有关系则跳出房间内循环，对下一房间进行判断</span></span><br><span class="line">				<span class="keyword">break</span>;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">if</span> (legal) &#123;</span><br><span class="line">				room[i][cnt[i]++] = curStu;	<span class="comment">//将合法考生安放在当前考场内</span></span><br><span class="line">				<span class="built_in">solve</span>(curStu + <span class="number">1</span>, roomNum);	<span class="comment">//在安排完毕上述考生后基于此房间进行下一个考生的安置</span></span><br><span class="line">				cnt[i]--;					<span class="comment">//若在下一考生未能安置在本房间，需要排除此考生并进入新房间</span></span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">//新建房间的操作</span></span><br><span class="line">		room[roomNum + <span class="number">1</span>][cnt[roomNum + <span class="number">1</span>]++] = curStu;</span><br><span class="line">		<span class="built_in">solve</span>(curStu + <span class="number">1</span>, roomNum + <span class="number">1</span>);</span><br><span class="line">		cnt[roomNum + <span class="number">1</span>]--;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">(<span class="type">int</span> argc, <span class="type">char</span>** argv)</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> ord;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;n, &amp;ord);</span><br><span class="line">	<span class="keyword">while</span> (ord--) &#123;</span><br><span class="line">		<span class="type">int</span> x, y;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;x, &amp;y);</span><br><span class="line">		relation[x][y] = relation[y][x] = <span class="number">1</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">solve</span>(<span class="number">1</span>, <span class="number">0</span>);	<span class="comment">//第一个考生必定新建房间，因此从0开始</span></span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, ans);</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h1 id="4-对局匹配"><a href="#4-对局匹配" class="headerlink" title="4.对局匹配"></a>4.对局匹配</h1><h2 id="4-1-问题描述"><a href="#4-1-问题描述" class="headerlink" title="4.1 问题描述"></a>4.1 问题描述</h2><p><font size=2 face="黑体"><br>　　小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分，代表他的围棋水平。小明发现网站的自动对局系统在匹配对手时，只会将积分差恰好是K的两名用户匹配在一起。如果两人分差小于或大于K，系统都不会将他们匹配。<br>　　现在小明知道这个网站总共有N名用户，以及他们的积分分别是A1, A2, … AN。<br>　　小明想了解最多可能有多少名用户同时在线寻找对手，但是系统却一场对局都匹配不起来(任意两名用户积分差不等于K)？</p>
<p>输入格式<br>　　第一行包含两个个整数N和K。<br>　　第二行包含N个整数A1, A2, … AN。<br>　　对于30%的数据，1 &lt;= N &lt;= 10<br>　　对于100%的数据，1 &lt;= N &lt;= 100000, 0 &lt;= Ai &lt;= 100000, 0 &lt;= K &lt;= 100000</p>
<p>输出格式<br>　　一个整数，代表答案。</p>
<p>样例输入<br>　　10 0<br>　　1 4 2 8 5 7 1 4 2 8</p>
<p>样例输出<br>　　6<br>&lt;/font&gt;  </p>
<h2 id="4-2-问题分析"><a href="#4-2-问题分析" class="headerlink" title="4.2 问题分析"></a>4.2 问题分析</h2><p>　　如果把n个元素按照分数相差为k的用户分为一组，例如：<br>　　第一组：{0,k,2k,3k,……}，<br>　　第二组：{1,k+1,k+2,k+3,……}，<br>　　……等等  </p>
<p>　　这样分组可以保证能各组之间不会被匹配，因为分叉不可能为k。因此可能匹配成功的玩家只可能从同组中产生，故只需在每个分组内尽量选取更多用户即可。使用cnt[score]表示分数为score的用户人数，假设现第i组有m个不同分数{x,x+k,x+2k,……,x+(m-1)k}，其中x表示该组的第一个人的积分，这里采用动态规划法来选择更多的人数。dp[j]表示前j个分数能够获得的最大用户（价值），很明显这里有两个选择：</p>
<p>　　1.选择j：dp[j] = dp[j-1];<br>　　2.不选j：dp[j] = dp[j-2] + cnt[score];</p>
<p>　　因此状态转义方程如下所示：<br>　　　　dp[i] = max{dp[i-1], dp[i-2] + cnt[score]}<br>　　　　其中score是此组中第i个分数值<br>　　需要注意的是，边界处（例如k=0）需要特殊处理  </p>
<h2 id="4-3-代码实现"><a href="#4-3-代码实现" class="headerlink" title="4.3 代码实现"></a>4.3 代码实现</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">define</span> _CRT_SECURE_NO_WARNINGS</span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="type">int</span> n, k;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> maxn = <span class="number">100000</span> + <span class="number">7</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> max_score = <span class="number">100000</span>;</span><br><span class="line"><span class="type">int</span> cnt[maxn];		<span class="comment">//cnt[score]表示积分为score的人数</span></span><br><span class="line"><span class="type">int</span> temp[maxn];</span><br><span class="line"><span class="type">int</span> dp[maxn];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">(<span class="type">int</span> argc, <span class="type">char</span>** argv)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">while</span> (<span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;n, &amp;k) == <span class="number">2</span>) &#123;</span><br><span class="line">		<span class="built_in">memset</span>(cnt, <span class="number">0</span>, <span class="built_in">sizeof</span>(cnt));</span><br><span class="line">		<span class="type">int</span> score, ans = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;score);</span><br><span class="line">			cnt[score]++;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span> (k == <span class="number">0</span>) &#123;		<span class="comment">//如果分差0即可匹配</span></span><br><span class="line">			<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; max_score; i++) &#123;</span><br><span class="line">				<span class="keyword">if</span> (cnt[i])  ans++;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> &#123;</span><br><span class="line">			<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; k; i++) &#123;	<span class="comment">//对于每积分组别</span></span><br><span class="line">				<span class="type">int</span> index = <span class="number">0</span>;</span><br><span class="line">				<span class="keyword">for</span> (<span class="type">int</span> j = i; j &lt; max_score; j += k) &#123;</span><br><span class="line">					temp[index++] = cnt[j];</span><br><span class="line">				&#125;</span><br><span class="line">				dp[<span class="number">0</span>] = temp[<span class="number">0</span>];</span><br><span class="line">				<span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">1</span>; j &lt; index; j++) &#123;</span><br><span class="line">					<span class="keyword">if</span> (j == <span class="number">1</span>)  dp[j] = <span class="built_in">max</span>(dp[<span class="number">0</span>], temp[j]);	<span class="comment">//边界</span></span><br><span class="line">					<span class="keyword">else</span>  dp[j] = <span class="built_in">max</span>(dp[j - <span class="number">1</span>], dp[j - <span class="number">2</span>] + temp[j]);</span><br><span class="line">				&#125;</span><br><span class="line">				ans += dp[index - <span class="number">1</span>];</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, ans);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>　　</p>
 
      <!-- reward -->
      
      <div id="reword-out">
        <div id="reward-btn">
          打赏
        </div>
      </div>
      
    </div>
    

    <!-- copyright -->
    
    <div class="declare">
      <ul class="post-copyright">
        <li>
          <i class="ri-copyright-line"></i>
          <strong>版权声明： </strong>
          
          本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
          
        </li>
      </ul>
    </div>
    
    <footer class="article-footer">
       
<div class="share-btn">
      <span class="share-sns share-outer">
        <i class="ri-share-forward-line"></i>
        分享
      </span>
      <div class="share-wrap">
        <i class="arrow"></i>
        <div class="share-icons">
          
          <a class="weibo share-sns" href="javascript:;" data-type="weibo">
            <i class="ri-weibo-fill"></i>
          </a>
          <a class="weixin share-sns wxFab" href="javascript:;" data-type="weixin">
            <i class="ri-wechat-fill"></i>
          </a>
          <a class="qq share-sns" href="javascript:;" data-type="qq">
            <i class="ri-qq-fill"></i>
          </a>
          <a class="douban share-sns" href="javascript:;" data-type="douban">
            <i class="ri-douban-line"></i>
          </a>
          <!-- <a class="qzone share-sns" href="javascript:;" data-type="qzone">
            <i class="icon icon-qzone"></i>
          </a> -->
          
          <a class="facebook share-sns" href="javascript:;" data-type="facebook">
            <i class="ri-facebook-circle-fill"></i>
          </a>
          <a class="twitter share-sns" href="javascript:;" data-type="twitter">
            <i class="ri-twitter-fill"></i>
          </a>
          <a class="google share-sns" href="javascript:;" data-type="google">
            <i class="ri-google-fill"></i>
          </a>
        </div>
      </div>
</div>

<div class="wx-share-modal">
    <a class="modal-close" href="javascript:;"><i class="ri-close-circle-line"></i></a>
    <p>扫一扫，分享到微信</p>
    <div class="wx-qrcode">
      <img src="//api.qrserver.com/v1/create-qr-code/?size=150x150&data=https://blog.shimmerjordan.eu.org/2020/01/21/practiceLanqiao/" alt="微信分享二维码">
    </div>
</div>

<div id="share-mask"></div>  
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E7%AE%97%E6%B3%95/" rel="tag">算法</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E7%BB%83%E4%B9%A0/" rel="tag">练习</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E8%AF%95%E9%A2%98/" rel="tag">试题</a></li></ul>

    </footer>
  </div>

   
  <nav class="article-nav">
    
      <a href="/2020/01/28/DSTOrder/" class="article-nav-link">
        <strong class="article-nav-caption">上一篇</strong>
        <div class="article-nav-title">
          
            饥荒指令
          
        </div>
      </a>
    
    
      <a href="/2020/01/18/AB/" class="article-nav-link">
        <strong class="article-nav-caption">下一篇</strong>
        <div class="article-nav-title">甘拜下风</div>
      </a>
    
  </nav>

   
<!-- valine评论 -->
<div id="vcomments-box">
  <div id="vcomments"></div>
</div>
<script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/valine@1.4.14/dist/Valine.min.js"></script>
<script>
  new Valine({
    el: "#vcomments",
    app_id: "StYfTMDp78X0EltFR16ve2q5-gzGzoHsz",
    app_key: "G4RPxRpXG6RwdfpnJefOSnyy",
    path: window.location.pathname,
    avatar: "wavatar",
    placeholder: "ヾﾉ≧∀≦)o来啊，快活啊!",
    recordIP: true,
  });
  const infoEle = document.querySelector("#vcomments .info");
  if (infoEle && infoEle.childNodes && infoEle.childNodes.length > 0) {
    infoEle.childNodes.forEach(function (item) {
      item.parentNode.removeChild(item);
    });
  }
</script>
<style>
  #vcomments-box {
    padding: 5px 30px;
  }

  @media screen and (max-width: 800px) {
    #vcomments-box {
      padding: 5px 0px;
    }
  }

  #vcomments-box #vcomments {
    background-color: #fff;
  }

  .v .vlist .vcard .vh {
    padding-right: 20px;
  }

  .v .vlist .vcard {
    padding-left: 10px;
  }
</style>

 
   
   
<!-- minivaline评论 -->
<div id="mvcomments-box">
  <div id="mvcomments"></div>
</div>
<script src="https://cdn.jsdelivr.net/npm/minivaline@latest"></script>
<script>
    new MiniValine(Object.assign({"enable":true,"mode":"DesertsP","placeholder":"Write a Comment","math":true,"md":true,"enableQQ":true,"NoRecordIP":false,"visitor":true,"maxNest":6,"pageSize":6,"adminEmailMd5":"de8a7aa53d07e6b6bceb45c64027763d","tagMeta":["管理员","小伙伴","访客"],"master":["de8a7aa53d07e6b6bceb45c64027763d"],"friends":["b5bd5d836c7a0091aa8473e79ed4c25e","adb7d1cd192658a55c0ad22a3309cecf","3ce1e6c77b4910f1871106cb30dc62b0","cfce8dc43725cc14ffcd9fb4892d5bfc"],"lang":null,"emoticonUrl":["https://cdn.jsdelivr.net/npm/alus@latest","https://cdn.jsdelivr.net/gh/MiniValine/qq@latest","https://cdn.jsdelivr.net/gh/MiniValine/Bilibilis@latest","https://cdn.jsdelivr.net/gh/MiniValine/tieba@latest","https://cdn.jsdelivr.net/gh/MiniValine/twemoji@latest","https://cdn.jsdelivr.net/gh/MiniValine/weibo@latest"]}, {
	  el: '#mvcomments',
    }));
  const infoEle = document.querySelector('#mvcomments .info');
  if (infoEle && infoEle.childNodes && infoEle.childNodes.length > 0) {
      infoEle.childNodes.forEach(function (item) {
          item.parentNode.removeChild(item);
      });
  }
</script>
<style>
	#mvcomments-box {
		padding: 5px 30px;
	}
	@media screen and (max-width: 800px) {
		#mvcomments-box {
		  padding: 5px 0px;
		}
	}
	.darkmode .MiniValine *{
		color: #f1f1f1!important;
	}
	.darkmode .commentTrigger{
		background-color: #403e3e !important;
	  }
	.darkmode .MiniValine .vpage .more{
		background: #21232F
	}
	.darkmode img{
		filter: brightness(30%)
	}
	.darkmode .MiniValine .vlist .vcard .vcomment-body .text-wrapper .vcomment.expand:before{
		background: linear-gradient(180deg, rgba(246,246,246,0), rgba(0,0,0,0.9))
	}
	.darkmode .MiniValine .vlist .vcard .vcomment-body .text-wrapper .vcomment.expand:after{
		background: rgba(0,0,0,0.9)
	}
	.darkmode .MiniValine .vlist .vcard .vcomment-body .text-wrapper .vcomment pre{
		background: #282c34
		border: 1px solid #282c34
	}
	.darkmode .MiniValine .vinputs-area .textarea-wrapper textarea{
		color: #000;
	}
	.darkmode .MiniValine .vinputs-area .auth-section .input-wrapper input{
		color: #000;
	}
	.darkmode .MiniValine .vinputs-area .vextra-area .vsmile-icons{
		background: transparent;
	}
	.darkmode .MiniValine .vinputs-wrap{
		border-color: #b2b2b5;
	}
	.darkmode .MiniValine .vinputs-wrap:hover{
		border: 1px dashed #2196f3;
	}
	.darkmode .MiniValine .vinputs-area .auth-section .input-wrapper{
		border-bottom: 1px dashed #b2b2b5;
	}
	.darkmode .MiniValine .vinputs-area .auth-section .input-wrapper:hover{
		border-bottom: 1px dashed #2196f3;
	}
	.darkmode .MiniValine .vbtn{
		background-color: transparent!important;
	}
	.darkmode .MiniValine .vbtn:hover{
		border: 1px dashed #2196f3;
	}
</style>

    
</article>

</section>
      <footer class="footer">
  <div class="outer">
    <ul>
      <li>
        Copyrights &copy;
        2019-2024
        <i class="ri-heart-fill heart_icon"></i> 鞠桥丹-QIAODAN JU
      </li>
    </ul>
    <ul>
      <li>
        
        
        
        由 <a href="https://hexo.io" target="_blank">Hexo</a> 强力驱动
        <span class="division">|</span>
        主题 - <a href="https://github.com/Shen-Yu/hexo-theme-ayer" target="_blank">Ayer</a>
        
      </li>
    </ul>
    <ul>
      <li>
        
        
        <span>
  <span><i class="ri-user-3-fill"></i>访问人数:<span id="busuanzi_value_site_uv"></span></s>
  <span class="division">|</span>
  <span><i class="ri-eye-fill"></i>浏览次数:<span id="busuanzi_value_page_pv"></span></span>
</span>
        
      </li>
    </ul>
    <ul>
      
    </ul>
    <ul>
      
    </ul>
    <ul>
      <li>
        <!-- cnzz统计 -->
        
        <script type="text/javascript" src='https://s4.cnzz.com/z_stat.php?id=1279035150&amp;web_id=1279035150'></script>
        
      </li>
    </ul>
  </div>
</footer>
      <div class="float_btns">
        <div class="totop" id="totop">
  <i class="ri-arrow-up-line"></i>
</div>

<div class="todark" id="todark">
  <i class="ri-moon-line"></i>
</div>

      </div>
    </main>
    <aside class="sidebar on">
      <button class="navbar-toggle"></button>
<nav class="navbar">
  
  <div class="logo">
    <a href="/"><img src="/images/ayer-side.svg" alt="丛烨-shimmerjordan"></a>
  </div>
  
  <ul class="nav nav-main">
    
    <li class="nav-item">
      <a class="nav-item-link" href="/">Home</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/archives">Catalogue</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags">Tags</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/%E9%9A%8F%E7%AC%94/">Essay</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/categories">Archives</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/friends">Friends</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/2020/01/18/about">About</a>
    </li>
    
  </ul>
</nav>
<nav class="navbar navbar-bottom">
  <ul class="nav">
    <li class="nav-item">
      
      <a class="nav-item-link nav-item-search"  title="搜索">
        <i class="ri-search-line"></i>
      </a>
      
      
      <a class="nav-item-link" target="_blank" href="/atom.xml" title="RSS Feed">
        <i class="ri-rss-line"></i>
      </a>
      
    </li>
  </ul>
</nav>
<div class="search-form-wrap">
  <div class="local-search local-search-plugin">
  <input type="search" id="local-search-input" class="local-search-input" placeholder="Search...">
  <div id="local-search-result" class="local-search-result"></div>
</div>
</div>
    </aside>
    <script>
      if (window.matchMedia("(max-width: 768px)").matches) {
        document.querySelector('.content').classList.remove('on');
        document.querySelector('.sidebar').classList.remove('on');
      }
    </script>
    <div id="mask"></div>

<!-- #reward -->
<div id="reward">
  <span class="close"><i class="ri-close-line"></i></span>
  <p class="reward-p"><i class="ri-cup-line"></i>请我喝杯蓝莓汁吧~</p>
  <div class="reward-box">
    
    <div class="reward-item">
      <img class="reward-img" src="/images/alipay.jpg">
      <span class="reward-type">支付宝</span>
    </div>
    
    
    <div class="reward-item">
      <img class="reward-img" src="/images/wechat.jpg">
      <span class="reward-type">微信</span>
    </div>
    
  </div>
</div>
    
<script src="/js/jquery-2.0.3.min.js"></script>


<script src="/js/lazyload.min.js"></script>

<!-- Tocbot -->


<script src="/js/tocbot.min.js"></script>

<script>
  tocbot.init({
    tocSelector: '.tocbot',
    contentSelector: '.article-entry',
    headingSelector: 'h1, h2, h3, h4, h5, h6',
    hasInnerContainers: true,
    scrollSmooth: true,
    scrollContainer: 'main',
    positionFixedSelector: '.tocbot',
    positionFixedClass: 'is-position-fixed',
    fixedSidebarOffset: 'auto'
  });
</script>

<script src="https://cdn.jsdelivr.net/npm/jquery-modal@0.9.2/jquery.modal.min.js"></script>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/jquery-modal@0.9.2/jquery.modal.min.css">
<script src="https://cdn.jsdelivr.net/npm/justifiedGallery@3.7.0/dist/js/jquery.justifiedGallery.min.js"></script>

<script src="/dist/main.js"></script>

<!-- ImageViewer -->

<!-- Root element of PhotoSwipe. Must have class pswp. -->
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">

    <!-- Background of PhotoSwipe. 
         It's a separate element as animating opacity is faster than rgba(). -->
    <div class="pswp__bg"></div>

    <!-- Slides wrapper with overflow:hidden. -->
    <div class="pswp__scroll-wrap">

        <!-- Container that holds slides. 
            PhotoSwipe keeps only 3 of them in the DOM to save memory.
            Don't modify these 3 pswp__item elements, data is added later on. -->
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>

        <!-- Default (PhotoSwipeUI_Default) interface on top of sliding area. Can be changed. -->
        <div class="pswp__ui pswp__ui--hidden">

            <div class="pswp__top-bar">

                <!--  Controls are self-explanatory. Order can be changed. -->

                <div class="pswp__counter"></div>

                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>

                <button class="pswp__button pswp__button--share" style="display:none" title="Share"></button>

                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>

                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>

                <!-- Preloader demo http://codepen.io/dimsemenov/pen/yyBWoR -->
                <!-- element will get class pswp__preloader--active when preloader is running -->
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                        <div class="pswp__preloader__cut">
                            <div class="pswp__preloader__donut"></div>
                        </div>
                    </div>
                </div>
            </div>

            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div>
            </div>

            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>

            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>

            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>

        </div>

    </div>

</div>

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/default-skin/default-skin.min.css">
<script src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe-ui-default.min.js"></script>

<script>
    function viewer_init() {
        let pswpElement = document.querySelectorAll('.pswp')[0];
        let $imgArr = document.querySelectorAll(('.article-entry img:not(.reward-img)'))

        $imgArr.forEach(($em, i) => {
            $em.onclick = () => {
                // slider展开状态
                // todo: 这样不好，后面改成状态
                if (document.querySelector('.left-col.show')) return
                let items = []
                $imgArr.forEach(($em2, i2) => {
                    let img = $em2.getAttribute('data-idx', i2)
                    let src = $em2.getAttribute('data-target') || $em2.getAttribute('src')
                    let title = $em2.getAttribute('alt')
                    // 获得原图尺寸
                    const image = new Image()
                    image.src = src
                    items.push({
                        src: src,
                        w: image.width || $em2.width,
                        h: image.height || $em2.height,
                        title: title
                    })
                })
                var gallery = new PhotoSwipe(pswpElement, PhotoSwipeUI_Default, items, {
                    index: parseInt(i)
                });
                gallery.init()
            }
        })
    }
    viewer_init()
</script>

<!-- MathJax -->

<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
      tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
      }
  });

  MathJax.Hub.Queue(function() {
      var all = MathJax.Hub.getAllJax(), i;
      for(i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
      }
  });
</script>

<script src="https://cdn.jsdelivr.net/npm/mathjax@2.7.6/unpacked/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script>
  var ayerConfig = {
    mathjax: true
  }
</script>

<!-- Katex -->

<!-- busuanzi  -->


<script src="/js/busuanzi-2.3.pure.min.js"></script>


<!-- ClickLove -->


<script src="/js/clickLove.js"></script>


<!-- ClickBoom1 -->

<!-- ClickBoom2 -->

<!-- CodeCopy -->


<link rel="stylesheet" href="/css/clipboard.css">

<script src="https://cdn.jsdelivr.net/npm/clipboard@2/dist/clipboard.min.js"></script>
<script>
  function wait(callback, seconds) {
    var timelag = null;
    timelag = window.setTimeout(callback, seconds);
  }
  !function (e, t, a) {
    var initCopyCode = function(){
      var copyHtml = '';
      copyHtml += '<button class="btn-copy" data-clipboard-snippet="">';
      copyHtml += '<i class="ri-file-copy-2-line"></i><span>COPY</span>';
      copyHtml += '</button>';
      $(".highlight .code pre").before(copyHtml);
      $(".article pre code").before(copyHtml);
      var clipboard = new ClipboardJS('.btn-copy', {
        target: function(trigger) {
          return trigger.nextElementSibling;
        }
      });
      clipboard.on('success', function(e) {
        let $btn = $(e.trigger);
        $btn.addClass('copied');
        let $icon = $($btn.find('i'));
        $icon.removeClass('ri-file-copy-2-line');
        $icon.addClass('ri-checkbox-circle-line');
        let $span = $($btn.find('span'));
        $span[0].innerText = 'COPIED';
        
        wait(function () { // 等待两秒钟后恢复
          $icon.removeClass('ri-checkbox-circle-line');
          $icon.addClass('ri-file-copy-2-line');
          $span[0].innerText = 'COPY';
        }, 2000);
      });
      clipboard.on('error', function(e) {
        e.clearSelection();
        let $btn = $(e.trigger);
        $btn.addClass('copy-failed');
        let $icon = $($btn.find('i'));
        $icon.removeClass('ri-file-copy-2-line');
        $icon.addClass('ri-time-line');
        let $span = $($btn.find('span'));
        $span[0].innerText = 'COPY FAILED';
        
        wait(function () { // 等待两秒钟后恢复
          $icon.removeClass('ri-time-line');
          $icon.addClass('ri-file-copy-2-line');
          $span[0].innerText = 'COPY';
        }, 2000);
      });
    }
    initCopyCode();
  }(window, document);
</script>


<!-- CanvasBackground -->


<script src="/js/dz.js"></script>



    
  </div>
</body>

</html>